#!/usr/bin/python3
# -*- coding: utf-8 -*-
u"""图相关算法练习."""
import os
from copy import deepcopy
from ticktock import ticktock


class Map(object):
    u"""构图和测试算法的类."""

    def __init__(self):
        u"""初始化构图，内置文件的."""
        # hsa-miR-429	ENSG00000004866.14    符合要求的广度搜索，测试目标
        # hsa-miR-200a-3p	ENSG00000136536.10      不符合要求，就应该搜不到的那种

        # 指定文件
        root_dir = os.path.dirname(__file__)
        self.miranda = os.path.join(root_dir, 'superdiff.miranda')
        self.tree, self.graph = self.generate_map()

    def generate_map(self):
        u"""抽取前一千行的文件，构成一个图，先构成一个有向图，随后转成一个无向图."""
        count = 0
        tree = {}
        with open(self.miranda) as f_:
            for line in f_:
                lines = line.split()

                tem = [lines[1]]
                if lines[0] in tree.keys():
                    tem.extend(tree[lines[0]])

                tree.update({lines[0]: tem})
                count += 1

                if count >= 1000:
                    break

        # 构建无向图，主要是将有向图，反过来，重新整合一遍
        graph = deepcopy(tree)
        for key, values in tree.items():
            for value in values:
                tem = [key]

                if value in graph.keys():
                    tem.extend(graph[value])

                graph.update({value: tem})

        return tree, graph

    '''
    http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/
    广度和深度搜索，受教育了，牛逼
    '''

    def dfs_search(self, start, target, path=None):
        u"""
        深度优先搜索.
        这个写法印证了我最开始的一些想法，只不过，我的那个写法面临着，如果遍历所有结果的问题，
        递归层面有一个问题没有处理好，就是结果的比对，我的是in和not in，那么就跳过这个结果，下一步继续判断其他的节点，之后保证返回准确路径就成了难题
        直接判断节点本身自然就不存在问题了，

        另一个问题是，我的递归，只能一层深下去，深的同时，如何保证路径提取的准确？难于登天，不好想，yield居家必备啊
        """
        if start not in self.graph.keys() or target not in self.graph.keys():
            raise KeyError(start, target)

        if path is None:
            path = [start]
        if start == target:
            yield path
        for next_ in set(self.graph[start]) - set(path):
            yield from self.dfs_search(next_, target, path + [next_])

    def bfs_search(self, start, goal):
        u"""广度优先搜索，大神写的是真厉害."""
        if start not in self.graph.keys() or goal not in self.graph.keys():
            raise KeyError(start, goal)

        queue = [(start, [start])]
        while queue:
            (vertex, path) = queue.pop(0)
            for next_ in set(self.graph[vertex]) - set(path):
                if next_ == goal:
                    yield path + [next_]
                else:
                    queue.append((next_, path + [next_]))

    @ticktock()
    def test_bfs(self):
        u"""测试广度优先算法."""
        for i in self.bfs_search('hsa-miR-429', 'hsa-miR-129-5p'):
            print(i)
            # continue

    @ticktock()
    def test_dfs(self):
        u"""测试深度优先算法."""
        for i in self.dfs_search('hsa-miR-429', 'hsa-miR-129-5p'):
            print(i)
            # continue


def __generate_new_map():
    u"""为迪克斯特拉算法生成新的图."""
    # 创建邻居和权重
    graph = {}
    # graph['you'] = ['alice', 'bob', 'claire']
    graph['start'] = {}
    graph['start']['a'] = 6
    graph['start']['b'] = 2

    graph['a'] = {}
    graph['a']['fin'] = 1

    graph['b'] = {}
    graph['b']['a'] = 3
    graph['b']['fin'] = 5

    graph['fin'] = {}

    return graph


def find_lowest_cost_node(graph, nodes):
    u"""找出这些节点中权重最低的路径."""
    lowest = [graph[x] for x in nodes]

    if not lowest:
        return []

    return [key for key, value in graph.items() if value == min(lowest)]


def dijsktra(graph, start, path=None, costs=0):
    u"""迪斯科特拉算法."""

    if path is None:
        path = [start]

    if len(graph[start]) <= 0:
        yield path, costs

    next_list = find_lowest_cost_node(
        graph[start], set(graph[start].keys()) - set(path))

    next_list += [x for x in graph[start].keys() if len(graph[x]) <= 0]

    for next_ in set(next_list):
        yield from dijsktra(graph, next_, path + [next_], costs + graph[start][next_])


def dijsktra2(graph, start):
    u"""外套一层，用来找出最短，且权重最低的路径的."""
    path = sorted([x for x in dijsktra(graph, start)], key=lambda x: x[1])
    return path[0]


def test():
    print(dijsktra2(__generate_new_map(), 'start'))


if __name__ == '__main__':
    test()
